/*
题目链接 : 
https://leetcode.cn/problems/fruits-into-baskets-iii/?slug=choose-k-elements-with-maximum-sum&tab=solutions&tab=3603047&tab=mei-ju-zuo-duan-dian-wei-hu-zui-xiao-ci-4nvu6&region=local_v2
*/

//题解代码:
class Solution {
public:
    #define N 400005
    int mx[N];
    void up(int i){
        mx[i] = max(mx[i<<1],mx[i<<1|1]);
    }
    void build(int l,int r,int i,vector<int>& b){
        if(l==r){
            mx[i] = b[l];
        }else{
            int mid = (l+r)/2;
            build(l,mid,i<<1,b);
            build(mid+1,r,i<<1|1,b);
            up(i);
        }
    }
    int query(int l,int r,int i,int target){
        if(l==r){
            return l;
        }else{
            int mid = (l+r)/2;
            if(mx[i<<1]>=target){
                return query(l,mid,i<<1,target);
            }else{
                return query(mid+1,r,i<<1|1,target);
            }
        }
    }
    void modiy(int l,int r,int i,int idx){
        if(l==r){
            mx[i] = 0;
        }else{
            int mid = (l+r)/2;
            if(idx<=mid){
                modiy(l,mid,i<<1,idx);
            }else{
                modiy(mid+1,r,i<<1|1,idx);
            }
            up(i);
        }
    }

    int numOfUnplacedFruits(vector<int>& a, vector<int>& b) {
        int n = a.size();
        int ans = 0;
        build(0,n-1,1,b);
        for(int i=0;i<n;++i){
            int x=a[i];
            if(mx[1]<x){
                ++ans;
                continue;
            }
            int idx = query(0,n-1,1,x);
            modiy(0,n-1,1,idx);
        }
        return ans;
    }
};
